Problem statement: zenit13ckh

Simonovi sa s pomocou umelej brady konečne podarilo dostať do trpasličej nory. Ako je známe, trpaslíci okrem pitia piva dolujú v útrobách hôr cenné kamene, ktoré by sa dali v meste speňažiť. Miestnosť, kde sa drahokamy ťažia je ale strážená prísne vyzerajúcim trpaslíkom.

Na vstup do baníckej časti nory je potrebné strážnikovi povedať heslo. Simon začul časť konverzácie medzi trpaslíkom vstupujúcim do bane a strážami. Na základe počutého vie, že heslo je jedno slovo a tiež začiatky niektorých slov, ktoré by ním mohli byť. Viac sa mu nepodarilo začuť, pretože z bane ho rušil hluk ťažobných nástrojov a z miestnosti vedľa ho rušil spev opitých trpaslíkov, ktorí zrovna nemajú službu.

Simonovi sa podarilo v nore nájsť výkladový slovník trpasličieho jazyka. Tento jazyk je podobný jazyku ľudí, ale jeho slovná zásoba je mierne odlišná. Rád by pre každý možný začiatok hesla vedel, koľko slov trpasličieho jazyka ním začína.

Na prvom riadku vstupu je počet slov v trpasličom jazyku N (podľa nájdeného slovníka). Na každom z ďalších N riadkoch je jedno z týchto slov. Tieto slová sú dlhé aspoň jeden a najviac 50 znakov a pozostávajú len z malých písmen anglickej abecedy. Môžete predpokladať, že sú všetky rôzne.

Na ďalšom riadku je počet možných začiatkov hesla M. Na zvyšných M riadkoch sú tieto začiatky. Všetky sú neprázdne, pozostávajú z najviac 50 znakov malej anglickej abecedy a sú rôzne. Platí 0 ≤ N ≤ 500,000 a 1 ≤ M ≤ 500,000.

Pre každého kandidáta w vypíšte na výstup jeden riadok s jedným číslom: počet slov v trpasličom jazyku takých, že w je ich prefixom. Platí, že w je prefixom v, ak existuje (aj prázdne) slovo u také, že wu = v. Napríklad slovo zenit má ako prefix prázdne slovo a slová z, ze, zen, zeni a zenit.

Okrem vzorového prístupu existujú aj pomalšie riešenia, ktoré získajú primeraný počet bodov. Na testovači máte okrem tu uvedených vstupov aj jeden väčší. V tejto úlohe neodporúčame použiť Python (negarantujeme, že môže získať plný počet bodov). Pamäťový limit v tejto úlohe je 2 GB.

4
antikvariat
antarktida
mantinel
anicka
3
ant
mantinely
antikv 

2
0
1 

4
aabb
aaabb
abb
aaaab
4
aab
a
aa
aabb 

1
4
3
1